package jutf8search;

import java.io.Serializable;
import java.util.Vector;
/**
 * The Knuth-Morris-Pratt algorithm implementing the jutf8search.Search interface.
 *
 */
@SuppressWarnings("serial")
public class KMP implements ExactSearchInterface, Serializable  {

	private int[] table;
	private byte[] query;
	private long match = 0;
	
	/*
	 *  (non-Javadoc)
	 * @see Search#matchNum(byte[], int)
	 */
	public long matchNum(byte[] text, long matchNum)
    {
		int i = 0;
		int m = 0;
		while(m+i < text.length)
        {
			if(query[i] == text[m+i]){
				++i;
				if(i == query.length) {
					++match;
					if(match == matchNum) return m;
					m += i;
					i=0;
				}
			}else{
				m = m + i - table[i];
				if(i > 0) i = table[i];	
			}
		}
		return -1;
	}
	
	/*
	 *  (non-Javadoc)
	 * @see Search#numMatches(byte[])
	 */
	public long numMatches(byte[] text){
		int i = 0;
		int m = 0;
		long matches = 0;
		while(m+i < text.length){
			if(query[i] == text[m+i]){
				++i;
				if(i == query.length)
				{
					++matches;
					m = m + i;
					i = 0;
				}
			}else{
				m = m + i - table[i];
				if(i > 0) i = table[i];
			}
		}
		return matches;
	}
	
	/*
	 *  (non-Javadoc)
	 * @see Search#numMatches(byte[])
	 */
	public Vector<Long> fullSearch(byte[] text)
    {
		int i = 0;
		int m = 0;
		Vector<Long> results = new Vector<Long>();
		while(m+i < text.length){
			if(query[i] == text[m+i]){
				++i;
				if(i == query.length)
				{
					results.add(new Long(m));
					m = m + i;
					i = 0;
				}
			}else{
				m = m + i - table[i];
				if(i > 0) i = table[i];
			}
		}
		return results;
	}

	/*
	 *  (non-Javadoc)
	 * @see Search#buildTable(java.lang.String)
	 */
	public void buildTable(String query) throws Exception
    {
		buildTable(Utilities.getBytes(query));
	}

	/*
	 *  (non-Javadoc)
	 * @see Search#buildTable(byte[])
	 */
	public void buildTable(byte[] query) throws Exception
    {
		if(query.length < 2) throw new Exception();
		int i, j;
		table = new int[query.length];
		this.query = query;
		i = 2;
		j = 0;
		table[0] = -1;
		table[1] = 0;
		while(i < query.length)
        {
			if(query[i-1] == query[j]){
				table[i] = j+1;
				++i;
				++j;
			}else if(j > 0){
				j = table[j];
			}else{
				table[i] = 0;
				++i;
			}
		}
	}

	/*
	 *  (non-Javadoc)
	 * @see Search#getPatternSize()
	 */
	public int getPatternSize() {
		return query.length;
	}
    
	/*
	 *  (non-Javadoc)
	 * @see Search#resetMatch()
	 */
	public void resetMatch() {
		match = 0;
	}

	




}
